The present invention relates generally to computer memory, and more particularly to tree traversal in a memory device.
Computer systems often require a considerable amount of high speed memory, such as random access memory (RAM), to hold information, such as data and programs, when a computer is powered and operational. Memory device demands have continued to grow as computer systems have increased in performance and complexity.
Some computer programs access large volumes of data, where the data itself may be organized in complex and dynamic data structures. Searching for data organized in complex data structures can be an intensive task for processing and memory systems. For example, a processing system that includes a cache memory system may experience a number of cache updates when searching a tree data structure that is widely distributed across a number of non-contiguous memory locations. Latency involved in numerous memory system accesses as well as evaluating numerous data values retrieved from the memory system can result in extended search times and reduced processing system throughput.